package com.leetcode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Solution {
    /**
     * 三数之和
     *
     * @param nums
     * @return
     */
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> list = new ArrayList<>();
        Arrays.sort(nums);
        int length = nums.length;
        for (int k = 0; k < length - 2; k++) {
            int i = k + 1;
            int j = length - 1;
            while (i < j) {
                int threeSum = nums[i] + nums[j] + nums[k];
                if (threeSum < 0) {
                    i++;
                } else if (threeSum > 0) {
                    j--;
                } else {
                    list.add(Arrays.asList(nums[k], nums[i], nums[j]));
                    while (i < j && nums[i] == nums[++i]) ;
                    while (i < j && nums[j] == nums[--j]) ;
                }
            }
            while (k < length - 2 && nums[k] == nums[++k]) ;
            k--;
        }
        return list;
    }

    /**
     * 返回两个正序数组的 中位数
     *
     * @param nums1
     * @param nums2
     * @return
     */
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int length1 = nums1.length;
        int length2 = nums2.length;
        int totalLen = length1 + length2;
        if (totalLen % 2 == 0) {
            return (getKthElement(nums1, nums2, totalLen / 2) + getKthElement(nums1, nums2, totalLen / 2 + 1)) * 0.5;
        }
        return getKthElement(nums1, nums2, totalLen / 2 + 1);
    }

    public int getKthElement(int[] num1, int[] num2, int k) {
        //表示数组的起始下标
        int index1 = 0;
        int index2 = 0;

        int length1 = num1.length;
        int length2 = num2.length;

        while (true) {
            //临界条件
            if (index1 == length1) { //说明num1这个被排除，则可以直接从num2找出目标值
                return num2[index2 + k - 1];
            }
            if (index2 == length2) { //说明num2这个被排除，则可以直接从num1找出目标值
                return num1[index1 + k - 1];
            }
            if (k == 1) {
                return Math.min(num1[index1], num2[index2]);
            }
            //中间值
            int half = k / 2;

            // 更新后新数组的第 k/2 个数的下标
            // 第 k/2 个数的下标有可能 大于 数组的长度，则需要用数组的最后一个元素
            int newIndex1 = Math.min(index1 + half, length1) - 1;
            int newIndex2 = Math.min(index2 + half, length2) - 1;

            //第 k/2 个数的值
            int pivot1 = num1[newIndex1];
            int pivot2 = num2[newIndex2];

            if (pivot1 <= pivot2) {
                //k表示第几小的数，如果k原本是7，排除3个，则k应该变为4
                //
                k -= (newIndex1 - index1 + 1);
                //因为newIndex指向第 k/2 个数的下标，次数被排除
                //index指向新数组的第一个元素
                index1 = newIndex1 + 1;
            } else {
                k -= (newIndex2 - index2 + 1);
                index2 = newIndex2 + 1;
            }
        }
    }

    /**
     * 生成有效括号
     *
     * @param n
     * @return
     */
    public List<String> generateParenthesis(int n) {
        List<String> list = new ArrayList<>();
        helpGenerate(list, "(", n - 1, 1);
        return list;
    }

    public void helpGenerate(List<String> list,
                             String curren, int nowLeft, int leftNoRight) {
        /**
         * 参数说明：
         * List<String> list:保存有效括号是列表
         * String curren：已经确定下来的括号。比如说已经确定了"(())",下一个只能是左括号
         * int nowLeft:剩下多少个左括号没有被插入。比如说总的三组括号，curren="()",则剩下两个左括号
         * int leftNoRight：curren中有多少个左括号没有 被 右括号 匹配的
         */
        while (nowLeft > 0) {
            if (leftNoRight > 0) {
                //当还有左括号没有被插入时，且curren存在 "(" 没有被 ")" 匹配，则curren可以插入'(',也可以插入')'
                //curren插入'(',利用函数递归里面会再生成一个curren
                helpGenerate(list, curren + "(", nowLeft - 1, leftNoRight + 1);
                //curren插入')'
                curren += ")";
                //被右括号匹配掉一个左括号，减1
                leftNoRight--;
            } else {
                //当还有左括号没有被插入，但是curren没有存在"(" 可以被 ")" 匹配，比如，curren="(())"
                //下一个插入只能是左括号
                curren += "(";
                //剩余左括号数减1
                nowLeft--;
                //未被右括号数加1
                leftNoRight++;
            }
        }
        //如果左括号已经全部插入，就补剩余的右括号
        for (int i = 0; i < leftNoRight; i++) {
            curren += ")";
        }
        //将每一遍函数内的curren存在list中
        list.add(curren);
    }

    /**
     * 最大正方形，返回其面积
     */
    public int maximalSquare(char[][] matrix) {
        //保存以matrix[i][j]为右下角的最大正方形的边长
        int[][] MaxSide = new int[matrix.length][matrix[0].length];

        //保存MaxSide中最大的数
        int max_side = 0;

        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[0].length; j++) {
                //如果为'0',则maxMatrix[i][j]为 0
                if (matrix[i][j] == '0') {
                    MaxSide[i][j] = 0;
                } else if (i > 0 && j > 0) { //matrix[i][j]为'1',且左上角matrix[i-1][j-1]存在
                    int t = MaxSide[i - 1][j - 1];
                    //t>0则需要判断横向和纵向是否都大于0
                    if (t > 0) {
                        //保存横向和纵向共同大于0的个数
                        int CR_max = 0;
                        //保存横向中大于0的个数
                        // int row_max = 0;
                        for (int k = 0; k < t; k++) {
                            //往左数，横向
                            if (MaxSide[i][j - k - 1] <= 0) {
                                //有一个小于0则不满足
                                break;
                            }
                            //往上数，纵向
                            if (MaxSide[i - k - 1][j] <= 0) {
                                //有一个小于0则不满足
                                break;
                            }
                            CR_max++;
                        }
                        MaxSide[i][j] = CR_max + 1;
                        max_side = Math.max(max_side, MaxSide[i][j]);
                    } else { //如果matrix[i-1][j-1] = 0
                        MaxSide[i][j] = 1;
                        max_side = Math.max(max_side, MaxSide[i][j]);
                    }
                } else { //如果 i = 0或j = 0，表示没有左上角的元素
                    MaxSide[i][j] = 1;
                    max_side = Math.max(max_side, MaxSide[i][j]);
                }
//                System.out.print(MaxSide[i][j] + " ");
            }
//            System.out.println();
        }
        return max_side * max_side;
    }
}
